package com.zjsru.leetcode75.level1.tree;

/**
 * @Author: cookLee
 * @Date: 2023-12-14
 * 路径总和 III
 */
public class PathSum {

    /**
     * 主
     * \
     * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
     * 输出：3
     * 解释：和等于 8 的路径有 3 条
     * \
     * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
     * 输出：3
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(10, new TreeNode(5, new TreeNode(3, new TreeNode(3), new TreeNode(2)), new TreeNode(2, null, new TreeNode(1))), new TreeNode(-3, null, new TreeNode(11)));
        PathSum pathSum = new PathSum();
        int targetSum = 8;
        System.out.println(pathSum.pathSum(tree,targetSum));
    }

    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){
            return 0;
        }
        //本级节点,使用长整型用来防止int类型溢出
        int ans = this.bfs(root, (long) targetSum);
        //左节点
        ans += this.pathSum(root.left, targetSum);
        //右节点
        ans += this.pathSum(root.right, targetSum);
        return ans;
    }

    /**
     * bfs
     *
     * @param targetSum 目标金额
     * @param root      根
     * @return int
     */
    private int bfs(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int ans = 0;
        //当时节点值等于目标值
        if (root.val == targetSum) {
            ans++;
        }
        //向左搜索，目标值为当前目标值减去当前节点值
        ans += this.bfs(root.left, targetSum - (long) root.val);
        //向右搜索同理
        ans += this.bfs(root.right, targetSum - (long) root.val);
        return ans;
    }

}
